package com.wxweven.algorithm.list.fastslow;

import com.wxweven.algorithm.list.ListNode;

/**
 * @author wxweven
 */
public class LC19删除链表倒数第k个结点 {

    /*
     * 1 -> 2 -> 3 -> 4 -> 5
     * 删除倒数第2个结点，变成：
     * 1 -> 2 -> 3 -> 5
     *
     * 分析：
     * 这个题跟求倒数第K个结点很类似，也是用快慢指针；区别在于，要删除一个结点，必须获取到前一个结点，
     * 所以，这里需要让快指针先走 k 步 而不是k-1步
     *
     * 还有就是要考虑删除的是head结点(k刚好和链表长度一样)的情况，删除head结点，一样也需要找到head结点的前一个结点
     * 所以，我们可以搞一个dummy结点，让 dummy.next = head
     * 而 slow 和 fast 都从 dummy结点开始走
     */

    public ListNode removeNthFromEnd(ListNode head, int k) {
        if (head == null) {
            return null;
        }

        // 考虑删除 head 结点的情况
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode fast = dummy;
        ListNode slow = dummy;

        // 让快指针先走 k 步
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }

        // fast走到结尾，循环退出，同时需要保证每一步fast都不为null
        while (fast != null && fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 移除倒数第 k 个结点
        slow.next = slow.next.next;

        // 注意，这里只能返回dummy.next，而不能返回head，因为head有可能被删除了
        // 不管是哪种情况，返回dummy.next都是对的
        return dummy.next;
    }
}